home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 3 / BBS in a box - Trilogy III.iso / Files / Prog / D-G / GemsI / Original / 2DClipping.c next >
Encoding:
Text File  |  1992-06-16  |  14.4 KB  |  753 lines  |  [TEXT/MPS ]
  1. /*
  2. Two-Dimensional Clipping: A Vector Based Approach
  3. by Hans Spoelder and Fons Ullings
  4. from "Graphics Gems", Academic Press, 1990
  5. */
  6.  
  7.  
  8. line.h
  9.  
  10. /*
  11.  * file line.h
  12.  *     contains major definitions for the clipping routines
  13.  *
  14.  */
  15. #define    NFAC        10        /* discrete measure    */
  16.     
  17. #define    SCALE        (1 << NFAC)    /* 1024 points/cm    */
  18. #define    TO_INT(X)    ((int)((X)*SCALE))
  19. #define    TO_FLT(X)    (((float)(X))/SCALE)
  20.  
  21. #define    COINCIDE        1        /* what do the lines do    */
  22. #define    PARALLEL        2
  23. #define    CROSS        3
  24. #define    NO_CROSS        4
  25.  
  26. #define    STD            0        /* crossing types    */
  27. #define    DELAY        1
  28.  
  29. #define    CLIP_NORMAL    1
  30.  
  31. typedef    struct    {        /* holds a point    */
  32.     long    _x;            /* holds x coordinate    */
  33.     long    _y;            /* holds y coordinate    */
  34. } POINT;
  35.  
  36. typedef    struct    {        /* holds a cross point    */
  37.     POINT    _p;            /* holds the solution    */
  38.     short    _type;        /* more information    */
  39. } CLIST;
  40.     
  41. struct    segment    {            /* holds a segment    */
  42.     POINT    _from;            /* start coordinates    */
  43.     POINT    _to;            /* stop coordinates    */
  44.     struct    segment    *_next;
  45.     struct    segment    *_prev;
  46. };
  47.  
  48.  
  49. #define    SEGMENT        struct segment
  50.  
  51. struct    contour {            /* holds a contour    */
  52.     short    _no;            /* contour counter    */
  53.     short    _status;            /* holds information    */
  54.     short    _cnt;            /* number of elements    */
  55.     SEGMENT    *_s;            /* the segments        */
  56.     struct    contour *_next;    /* linked list        */
  57.     long    _minx;            /* coordinates of box    */
  58.     long    _miny;
  59.     long    _maxx;
  60.     long    _maxy;
  61. };
  62.  
  63. #define    CONTOUR        struct contour
  64.  
  65. #define    ACTIVE        01        /* polygon attributes    */
  66. #define    NORMAL        02
  67.  
  68. #define    SET_ON(p)    ((p)->_status |=  ACTIVE)
  69. #define    SET_NORMAL(p)    ((p)->_status |= NORMAL)
  70.  
  71. #define    SET_OFF(p)    ((p)->_status &= ~ACTIVE)
  72. #define    SET_INVERSE(p)    ((p)->_status &= ~NORMAL)
  73.  
  74. #define    IS_ON(p)    ((p)->_status & ACTIVE)
  75. #define    IS_NORMAL(p)    ((p)->_status & NORMAL)
  76.  
  77. extern    CONTOUR    *CL;
  78.  
  79. CONTOUR    *get_contour_ptr();
  80.  
  81. extern    short    C_COUNT;
  82.  
  83. box.h
  84.  
  85. /* 
  86.  * file box.h
  87.  *    a short include file is better then no include file
  88.  */
  89. typedef    struct    {        /* guess what this is        */
  90.     long    _lowx;
  91.     long    _lowy;
  92.     long    _highx;
  93.     long    _highy;
  94. } BOX;
  95.  
  96.  
  97. bio1.c
  98.  
  99. /*
  100.  * file  bio.c
  101.  *    contains the basic operations
  102.  *
  103.  */
  104. #include    <stdio.h>
  105. #include    "line.h"
  106.  
  107. /*
  108.  * def_contour
  109.  *
  110.  *    Purpose:
  111.  *    add a contour to the list
  112.  *    NOTE: coordinates must already be converted into longs!
  113.  *    
  114.  *    x    x coordinates of the end points of segments
  115.  *    y    y coordinates of the end points of segments
  116.  *    n    number of coordinate pairs
  117.  *    no    contour number (id), does no have to be unique!
  118.  *    type    type of clip operation desired CLIP_NORMAL means
  119.  *        clip everything inside the contour
  120.  */
  121. def_contour(x, y, n, no, type)
  122. long    x[], y[];
  123. int    n, no, type;
  124. {
  125.     short    i;
  126.     long    dx1, dx2, dy1, dy2;
  127.     long    minx, miny, maxx, maxy;
  128.     CONTOUR    *cp;
  129.     SEGMENT    *sp, *spp;
  130.  
  131.     if((cp = CL) == (CONTOUR *)NULL) {
  132.         cp = CL = NEWTYPE(CONTOUR);
  133.     }
  134.     else {
  135.         while(cp->_next != (CONTOUR *)NULL)
  136.             cp = cp->_next;
  137.         i = cp->_no;
  138.         cp = cp->_next = NEWTYPE(CONTOUR);
  139.     }
  140.  
  141.     cp->_next = (CONTOUR *)NULL;
  142.     cp->_no = no;
  143.     SET_ON(cp);
  144.     if(type == CLIP_NORMAL)
  145.         SET_INVERSE(cp);
  146.     else
  147.         SET_NORMAL(cp);
  148.     minx = miny = 1000000;
  149.     maxx = maxy = -1;
  150.     for(i=0; i<n; i++) {
  151.         if(i == 0) {
  152.             cp->_s = sp = NEWTYPE(SEGMENT);
  153.             sp->_from._x = x[0];
  154.             sp->_from._y = y[0];
  155.             sp->_to._x   = x[1];
  156.             sp->_to._y   = y[1];
  157.         }
  158.         else {
  159.         /*
  160.          * if necessary stretch the contour
  161.          * and skip the point
  162.          */
  163.             dx1 = sp->_to._x - sp->_from._x;
  164.             dy1 = sp->_to._y - sp->_from._y;
  165.             dx2 = x[(i == n-1) ? 0 : i+1] - sp->_to._x;
  166.             dy2 = y[(i == n-1) ? 0 : i+1] - sp->_to._y;
  167.             if(dy2*dx1 == dy1*dx2) {
  168.                 sp->_to._x = x[(i == n-1) ? 0 : i+1];
  169.                 sp->_to._y = y[(i == n-1) ? 0 : i+1];
  170.             }
  171.             else {
  172.                 spp = sp;
  173.                 sp = sp->_next =  NEWTYPE(SEGMENT);
  174.                 sp->_prev = spp;
  175.                 sp->_from._x = x[i];
  176.                 sp->_from._y = y[i];
  177.                 sp->_to._x = x[(i == n-1) ? 0 : i+1];
  178.                 sp->_to._y = y[(i == n-1) ? 0 : i+1];
  179.             }
  180.         }
  181.  
  182. /*
  183.  * calculate the enclosing box
  184.  */
  185.         if(x[i] < minx) 
  186.             minx = x[i];
  187.         if(x[i] > maxx)
  188.             maxx = x[i];
  189.         if(y[i] < miny)
  190.             miny = y[i];
  191.         if(y[i] > maxy)
  192.             maxy = y[i];
  193.             
  194.     }
  195.     cp->_minx = minx;
  196.     cp->_maxx = maxx;
  197.     cp->_miny = miny;
  198.     cp->_maxy = maxy;
  199.     sp->_next = cp->_s;
  200.     cp->_s->_prev = sp;
  201.     cp->_next = (CONTOUR *)NULL;
  202. }
  203.  
  204. /*
  205.  * get_contour_ptr
  206.  *
  207.  *    PURPOSE
  208.  *    get the pointer to a contour given its id
  209.  *    with multiple id's first fit algorithm is
  210.  *    used. Returns NULL in case of error.
  211.  *
  212.  *    no    id of contour
  213.  */
  214. CONTOUR    *get_contour_ptr(no)
  215. int    no;
  216. {
  217.     CONTOUR    *cp;
  218.  
  219.     if((cp = CL) == (CONTOUR *)NULL) 
  220.         return((CONTOUR *)NULL);
  221.     else {
  222.         while(cp != (CONTOUR *)NULL) {
  223.             if(cp->_no == no)
  224.                 return(cp);
  225.             else
  226.                 cp = cp->_next;
  227.         }
  228.         return((CONTOUR *)NULL);
  229.     }
  230. }
  231.  
  232.  
  233. /*
  234.  * del_contour
  235.  *
  236.  *    PURPOSE
  237.  *    delete contour(s) from the list with id
  238.  *    no
  239.  */
  240. del_contour(no)
  241. int    no;
  242. {
  243.     CONTOUR    *cp, *cpp;
  244.     CONTOUR    *qp = (CONTOUR *)NULL;
  245.     SEGMENT    *sp, *spp;
  246.  
  247.     if((cp = CL) == (CONTOUR *)NULL)
  248.         return;
  249.     while(cp != (CONTOUR *)NULL) {
  250.         if(cp->_no == no) {
  251.             sp = cp->_s;
  252.             do {
  253.                 spp = sp->_next;
  254.                 free(sp);
  255.                 sp = spp;
  256.             } while(sp != cp->_s);
  257.             cpp = cp->_next;
  258.             free(cp);
  259.             if(qp)
  260.                 qp->_next = cpp;
  261.             else
  262.                 CL = cpp;
  263.             cp = cpp;
  264.         } 
  265.         else {
  266.             qp = cp;
  267.             cp = cp->_next;
  268.         }
  269.     }
  270. }
  271.  
  272.  
  273. cross1.c
  274.  
  275. /*
  276.  * file cross.c:
  277.  *    calculate the intersections
  278.  */
  279. #include    <math.h>
  280. #include    "line.h"
  281. #include    "box.h"
  282. /*
  283.  * cross_calc:
  284.  *
  285.  *    PURPOSE
  286.  *    calculate the intersections between the polygon
  287.  *    stored in poly and the linesegment stored in l
  288.  *    and put the intersections into psol.
  289.  *
  290.  *    poly    pointer to the structure containing the polygon
  291.  *    l    pointer to the structure containing the linesegment
  292.  *    psol    pointer to the pointer where intersections are stored
  293.  *    nsol    current number of intersections stored
  294.  *    nsmax    maximum storage in psol for intersections
  295.  *        if nsol exceeds nsmax additional storage is allocated
  296.  *
  297.  */
  298. cross_calc(poly, l, psol, nsol, nsmax)
  299. CONTOUR    *poly;
  300. SEGMENT    *l;
  301. CLIST    **psol;
  302. short    *nsol, nsmax;
  303. {
  304.     SEGMENT    *p;
  305.     CLIST    *sol;
  306.     double    s;
  307.     long    x, y, a, b, c;
  308.     int    psort(), type;
  309.  
  310.     sol = *psol;
  311.     p = poly->_s;
  312.     do {
  313. /*
  314.  * calculate the a, b and c coefficients and determine the
  315.  * type of intersection
  316.  */
  317.  
  318.         a = (p->_to._y - p->_from._y)*(l->_to._x - l->_from._x) -
  319.             (p->_to._x - p->_from._x)*(l->_to._y - l->_from._y);
  320.         b = (p->_from._x - l->_from._x)*(l->_to._y - l->_from._y) -
  321.             (p->_from._y - l->_from._y)*(l->_to._x - l->_from._x);
  322.         c = (p->_from._x - l->_from._x)*(p->_to._y - p->_from._y) -
  323.             (p->_from._y - l->_from._y)*(p->_to._x - p->_from._x);
  324.         if(a == 0)
  325.             type = (b == 0) ? COINCIDE : PARALLEL;
  326.         else {
  327.             if(a > 0) {
  328.                 if((b >= 0 && b <= a) &&
  329.                    (c >= 0 && c <= a))
  330.                     type = CROSS;
  331.                 else
  332.                     type = NO_CROSS;
  333.             }
  334.             else {
  335.                 if((b <= 0 && b >= a) &&
  336.                    (c <= 0 && c >= a))
  337.                     type = CROSS;
  338.                 else
  339.                     type = NO_CROSS;
  340.             }
  341.         }
  342. /*
  343.  * process the interscetion found
  344.  */
  345.         switch(type) {
  346.             case NO_CROSS: case PARALLEL:
  347.                 break;
  348.  
  349.             case CROSS:
  350.                 if(b == a || c == a || c == 0)
  351.                     break;
  352.                 if(b == 0 && 
  353.                    p_where(&(p->_prev->_from), &(p->_to), l) >= 0)
  354.                     break;
  355.                 s = (double)b/(double)a;
  356.                 if(l->_from._x == l->_to._x)
  357.                     x = l->_from._x;
  358.                 else
  359.                     x = p->_from._x + 
  360.                        (int)((p->_to._x - p->_from._x)*s);
  361.                 if(l->_from._y == l->_to._y)
  362.                     y = l->_from._y;
  363.                 else
  364.                     y = p->_from._y + 
  365.                        (int)((p->_to._y - p->_from._y)*s);
  366.  
  367.                 if(*nsol == nsmax) {
  368.                     nsmax *= 2;
  369.                     *psol = sol = (CLIST *) realloc(sol,                             nsmax*sizeof(CLIST)); 
  370.                 }
  371.                 sol[*nsol]._p._x = x;
  372.                 sol[*nsol]._p._y = y;
  373.                 sol[*nsol]._type = STD;
  374.                 *nsol += 1;
  375.                 break;
  376.  
  377.             case COINCIDE:
  378.                 if(p_where(&(p->_prev->_from),
  379.                      &(p->_next->_to), l) > 0)
  380.                     break;
  381.                 if(l->_from._x != l->_to._x) {
  382.                     if((max(l->_from._x, l->_to._x) <
  383.                         min(p->_from._x, p->_to._x)  ) ||
  384.                        (min(l->_from._x, l->_to._x) >
  385.                         max(p->_from._x, p->_to._x))   )
  386.                         break;
  387.                     if(min(l->_from._x, l->_to._x) <
  388.                        min(p->_from._x, p->_to._x) ) {
  389.                         if(*nsol == nsmax) {
  390.                             nsmax *= 2;
  391.                             *psol = sol = (CLIST *) realloc(sol,                                 nsmax*sizeof(CLIST));
  392.                         }
  393.                         sol[*nsol]._p._x = p->_from._x;
  394.                         sol[*nsol]._p._y = p->_from._y;
  395.                         sol[*nsol]._type = DELAY;
  396.                         *nsol += 1;
  397.                     }
  398.                     if(max(l->_from._x, l->_to._x) >
  399.                        max(p->_from._x, p->_to._x) ) {
  400.                         if(*nsol == nsmax) {
  401.                             nsmax *= 2;
  402.                             *psol = sol = (CLIST *) realloc(sol,                                 nsmax*sizeof(CLIST));
  403.                         }
  404.                         sol[*nsol]._p._x = p->_to._x;
  405.                         sol[*nsol]._p._y = p->_to._y;
  406.                         sol[*nsol]._type = DELAY;
  407.                         *nsol += 1;
  408.                     }
  409.                 }
  410.                 else {
  411.  
  412.                     if((max(l->_from._y, l->_to._y) <
  413.                         min(p->_from._y, p->_to._y)  ) ||
  414.                        (min(l->_from._y, l->_to._y) >
  415.                         max(p->_from._y, p->_to._y)) )
  416.                         break;
  417.                     if(min(l->_from._y, l->_to._y) <
  418.                        min(p->_from._y, p->_to._y) ) {
  419.                         if(*nsol == nsmax) {
  420.                             nsmax *= 2;
  421.                             *psol = sol = (CLIST *) realloc(sol,                                 nsmax*sizeof(CLIST));
  422.                         }
  423.                         sol[*nsol]._p._x = p->_from._x;
  424.                         sol[*nsol]._p._y = p->_from._y;
  425.                         sol[*nsol]._type = DELAY;
  426.                         *nsol += 1;
  427.                     }
  428.                     if(max(l->_from._y, l->_to._y) >
  429.                        max(p->_from._y, p->_to._y) ) {
  430.                         if(*nsol == nsmax) {
  431.                             nsmax *= 2;
  432.                             *psol = sol = (CLIST *) realloc(sol,                                 nsmax*sizeof(CLIST));
  433.                         }
  434.                         sol[*nsol]._p._x = p->_to._x;
  435.                         sol[*nsol]._p._y = p->_to._y;
  436.                         sol[*nsol]._type = DELAY;
  437.                         *nsol += 1;
  438.                     }
  439.                 }
  440.                 break;
  441.         }
  442.         p = p->_next;
  443.     } while(p != poly->_s);
  444.     qsort(sol, *nsol, sizeof(CLIST), psort);
  445. }
  446.  
  447.  
  448. /*
  449.  * p_where
  450.  *
  451.  *    PURPOSE
  452.  *    determine position of point p1 and p2 relative to
  453.  *    linesegment l. 
  454.  *    Return value
  455.  *    < 0    p1 and p2 lie at different sides of l
  456.  *    = 0    one of both points lie on l
  457.  *    > 0    p1 and p2 lie at same side of l
  458.  *
  459.  *    p1    pointer to coordinates of point
  460.  *    p2    pointer to coordinates of point
  461.  *    l    pointer to linesegment
  462.  * 
  463.  */
  464. p_where(p1, p2, l)
  465. POINT    *p1, *p2;
  466. SEGMENT    *l;
  467. {
  468.     long    dx, dy, dx1, dx2, dy1, dy2, p_1, p_2;
  469.  
  470.     dx  = l->_to._x - l->_from._x;
  471.     dy  = l->_to._y - l->_from._y;
  472.     dx1 = p1->_x - l->_from._x;
  473.     dy1 = p1->_y - l->_from._y;
  474.     dx2 = p2->_x - l->_to._x;
  475.     dy2 = p2->_y - l->_to._y;
  476.     p_1 = (dx*dy1 - dy*dx1);
  477.     p_2 = (dx*dy2 - dy*dx2);
  478.     if(p_1 == 0 || p_2 == 0)
  479.         return(0);
  480.     else {
  481.         if((p_1 > 0 && p_2 < 0) || (p_1 < 0 && p_2 > 0))
  482.             return(-1);
  483.         else
  484.             return(1);
  485.     }
  486. }
  487.  
  488.  
  489. /*
  490.  * p_inside
  491.  *
  492.  *    PURPOSE
  493.  *    determine if the point stored in pt lies inside
  494.  *    the polygon stored in p
  495.  *    Return value:
  496.  *    FALSE    pt lies outside p
  497.  *    TRUE    pt lies inside  p
  498.  *
  499.  *    p    pointer to the polygon
  500.  *    pt    pointer to the point
  501.  */    
  502. boolean    p_inside(p, pt)
  503. CONTOUR    *p;
  504. POINT    *pt;
  505. {
  506.     SEGMENT    l, *sp;
  507.     CLIST    *sol;
  508.     short    nsol = 0, nsmax = 2, reduce = 0, i;
  509.     boolean    on_contour(), odd;
  510.     
  511.     l._from._x = p->_minx-2;
  512.     l._from._y = pt->_y;
  513.     l._to._x   = pt->_x;
  514.     l._to._y   = pt->_y;
  515.     sol = (CLIST *) calloc(2, sizeof(CLIST));
  516.     cross_calc(p, &l, &sol, &nsol, nsmax);
  517.     for(i=0; i<nsol-1; i++)
  518.         if(sol[i]._type == DELAY && sol[i+1]._type == DELAY)
  519.             reduce++;
  520.     free(sol);
  521.     odd = (nsol - reduce) & 0x01;
  522.     return(odd ? !on_contour(p, pt) : FALSE);
  523. }
  524.  
  525. /*
  526.  * function used for sorting
  527.  */
  528. psort(p1, p2)
  529. CLIST    *p1, *p2;
  530. {
  531.     if(p1->_p._x != p2->_p._x)
  532.         return(p1->_p._x - p2->_p._x);
  533.     else 
  534.         return(p1->_p._y - p2->_p._y);
  535. }
  536.  
  537.  
  538. /*
  539.  * on_contour
  540.  *
  541.  *    PURPOSE
  542.  *    determine if the point pt lies on the
  543.  *    contour p.
  544.  *    Return value
  545.  *    TRUE     point lies on contour
  546.  *    FALSE    point lies not on contour
  547.  *
  548.  *    p    pointer to the polygon structure
  549.  *    pt    pointer to the point
  550.  */
  551. boolean    on_contour(p, pt)
  552. CONTOUR    *p;
  553. POINT    *pt;
  554. {
  555.     SEGMENT    *sp;
  556.     long    dx1, dy1, dx2, dy2;
  557.  
  558.     sp = p->_s;
  559.     do {
  560.         if((pt->_x >= min(sp->_from._x, sp->_to._x)) &&
  561.            (pt->_x <= max(sp->_from._x, sp->_to._x))    ) { 
  562.             dx1 = pt->_x - sp->_from._x;
  563.             dx2 = sp->_to._x - pt->_x;
  564.             dy1 = pt->_y - sp->_from._y;
  565.             dy2 = sp->_to._y - pt->_y;
  566.             if(dy1*dx2 == dy2*dx1)
  567.                 return(TRUE);
  568.         }
  569.         sp = sp->_next;
  570.     } while(sp != p->_s);
  571.     return(FALSE);
  572. }
  573.  
  574. clip1.c
  575.  
  576. /*
  577.  * file clip.c
  578.  *    contains the actual clipping routines
  579.  */
  580. #include    <stdio.h>
  581. #include    "line.h"
  582.  
  583.  
  584. /*
  585.  * vis_vector
  586.  *
  587.  *    PURPOSE
  588.  *    actual user interface. Draws a clipped line
  589.  *    NOTE: coordinates are given in converted LONGS!
  590.  *
  591.  *    xf, yf    from coordinates of vector to be drawn
  592.  *    xt, yt    to coordinates of vector to be drawn
  593.  */
  594. vis_vector(xf, yf, xt, yt)
  595. long    xf, yf, xt, yt;
  596. {
  597.     SEGMENT    l;
  598.  
  599.     if(xf == xt && yf == yt)
  600.         return;
  601.     l._from._x = xf;
  602.     l._from._y = yf;
  603.     l._to._x   = xt;
  604.     l._to._y   = yt;
  605. /*
  606.  * start at top of list
  607.  */
  608.     clip(CL, &l);
  609. }
  610.  
  611. /*
  612.  * clip
  613.  *
  614.  *    PURPOSE
  615.  *
  616.  *    p    pointer to polygon
  617.  *    l    pointer to line segment
  618.  */
  619. clip(p, l)
  620. CONTOUR    *p;
  621. SEGMENT    *l;
  622. {
  623.     SEGMENT    *sp, ss;
  624.     CLIST    *sol;
  625.     POINT    pt;
  626.     boolean    up, delay, inside, p_inside(), disjunct();
  627.     int    i;
  628.     short    nsol, nsmax = 2;
  629.  
  630.  
  631. /*
  632.  * list exhausted do what you like
  633.  * we want to plot
  634.  */
  635.     if(p == (CONTOUR *)NULL) {
  636.         move((l->_from._x), (l->_from._y));
  637.         cont((l->_to._x), (l->_to._y));
  638.         return;
  639.     }
  640. /*
  641.  * polygon is switched off
  642.  * take next one
  643.  */
  644.     if(!IS_ON(p)) {
  645.         clip(p->_next, l);
  646.         return;
  647.     }
  648. /*
  649.  * comparison on basis of the
  650.  * enclosing rectangle
  651.  */
  652.     if(disjunct(p, l)) {
  653.         if(!IS_NORMAL(p)) {
  654.             clip(p->_next, l);
  655.         }
  656.         return;
  657.     }
  658. /*
  659.  * calculate possible intersections
  660.  */
  661.     sol = (CLIST *) calloc(2, sizeof(CLIST));
  662.     sol[0]._p._x = l->_from._x;
  663.     sol[0]._p._y = l->_from._y;
  664.     sol[0]._type = STD;
  665.     sol[1]._p._x = l->_to._x;
  666.     sol[1]._p._y = l->_to._y;
  667.     sol[1]._type = STD;
  668.     nsol = 2;
  669.     cross_calc(p, l, &sol, &nsol, nsmax);
  670.     pt._x = sol[0]._p._x;
  671.     pt._y = sol[0]._p._y;
  672.  
  673. /*
  674.  * determine status of first point
  675.  */
  676.     inside = p_inside(p, &pt);
  677.     if((!inside && IS_NORMAL(p)) || (inside && !IS_NORMAL(p)))
  678.         up = TRUE; 
  679.     else
  680.         up = FALSE;
  681.     delay = FALSE;
  682. /*
  683.  * process list of intersections
  684.  */
  685.     for(i=1; i<nsol; i++) {
  686.         if(!up) {
  687.             ss._from._x = sol[i-1]._p._x;
  688.             ss._from._y = sol[i-1]._p._y;
  689.             ss._to._x = sol[i]._p._x;
  690.             ss._to._y = sol[i]._p._y;
  691.             clip(p->_next, &ss);
  692.         }
  693.         if(!delay) {
  694.             if(sol[i]._type != DELAY)
  695.                 up = (up) ? FALSE : TRUE
  696.             else
  697.                 delay = TRUE;
  698.         }
  699.         else {
  700.             up = (up) ? FALSE : TRUE;
  701.             delay = FALSE;
  702.         }
  703.     }
  704.     free(sol);
  705. }
  706.  
  707. /*
  708.  * disjunct
  709.  *
  710.  *    PURPOSE
  711.  *    determine if the box enclosing the polygon 
  712.  *    stored in p and the box enclosing the line 
  713.  *    segment stored in l are disjunct.
  714.  *    Return TRUE if disjunct else FALSE
  715.  *
  716.  *    p    points to the polygon structure
  717.  *    l    points to the linesegment structure    
  718.  *
  719.  */
  720. boolean    disjunct(p, l)
  721. CONTOUR    *p;
  722. SEGMENT    *l;
  723.  
  724. {
  725.     if((max(l->_from._x, l->_to._x) < p->_minx) ||
  726.        (min(l->_from._x, l->_to._x) > p->_maxx) ||
  727.            (max(l->_from._y, l->_to._y) < p->_miny) ||
  728.        (min(l->_from._y, l->_to._y) > p->_maxy)   )
  729.         return(TRUE);
  730.     else
  731.         return(FALSE);
  732. }
  733.  
  734. #define DEBUG
  735. #ifdef DEBUG
  736. move(x, y)
  737. long    x, y;
  738. {
  739.     printf("(%d,%d) ->", x, y);
  740. }
  741.  
  742. cont(x, y)
  743. long    x, y;
  744. {
  745.     printf("(%d,%d)\n", x, y);
  746. }
  747.  
  748. #endif
  749.  
  750.  
  751.  
  752.  
  753.